package com.djzhu.algorithm.sort;

/**
 * Descriptions...
 *
 * @author DJ.Zhu
 */
public class QuickSort extends AbstractSort{

    @Override
    public void sort(Integer[] arr) {
        doSort(arr, 0, arr.length - 1);
    }

    private void doSort(Integer[] arr, Integer low, Integer high) {
        int l=low;
        int h=high;
        int povit=arr[low];

        while(l<h) {
            while(l<h&&arr[h]>=povit)
                h--;
            if(l<h){
//                arr[l]=arr[h];
                swap(arr, l, h);
//                l++;
            }

            while(l<h&&arr[l]<=povit)
                l++;

            if(l<h){
//                arr[h]=arr[l];
                swap(arr, l, h);
//                h--;
            }
        }
//        arr[l]=povit;
        print(arr);
        System.out.println("l="+(l)+", h="+(h)+", povit="+povit);
        if(l-1>low)doSort(arr,low,l-1);
        if(h+1<high)doSort(arr,h+1,high);
    }
}
